package com.zhugang.week13.prefixsuffixstatistics;

/**
 * @program algorithms
 * @description: ProductExceptSelf
 * @author: chanzhugang
 * @create: 2022/09/23 19:21
 */
public class ProductExceptSelf {

    /**
     * 238 除自身外数组的乘积
     * https://leetcode.cn/problems/product-of-array-except-self/
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf(int[] nums) {
        // 前缀、后缀乘积统计
        int n = nums.length;

        int[] leftProduts = new int[n];
        int product = 1;
        for (int i = 0; i < n; i++) {
            product *= nums[i];
            // 前缀乘积
            leftProduts[i] = product;
        }

        product = 1;
        int[] rightProducts = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            product *= nums[i];
            // 后缀乘积
            rightProducts[i] = product;
        }

        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = 1;
            if (i - 1 >= 0) {
                result[i] *= leftProduts[i - 1];
            }
            if (i + 1 < n) {
                // 当前求解
                result[i] *= rightProducts[i + 1];
            }
        }
        return result;
    }

    /**
     * 空间复杂度O(1)
     *
     * @param nums
     * @return
     */
    public int[] productExceptSelf2(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];

        int leftProduct = 1;
        for (int i = 0; i < n; i++) {
            // 乘积不包含第i个元素
            result[i] = leftProduct;
            leftProduct *= nums[i];
        }

        int rightProduct = 1;

        for (int i = n - 1; i >= 0; i--) {
            // i-1个元素的乘积 * i右边元素
            result[i] *= rightProduct;
            rightProduct *= nums[i];
        }
        return result;
    }

}